//-----------------------------------------------------------------------------
// File: Linklist.h
// Desc: Linked list class.
//
// THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF
// ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO
// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
// PARTICULAR PURPOSE.
//
//  Copyright (C) Microsoft Corporation. All rights reserved.
//-----------------------------------------------------------------------------

#pragma once

// Notes:
// 
// The List class template implements a simple double-linked list. 
// It uses STL's copy semantics. 

// There are two versions of the Clear() method:
//  Clear(void) clears the list w/out cleaning up the object.
//  Clear(FN fn) takes a functor object that releases the objects, if they need cleanup.

// The List class supports enumeration. Example of usage:
//
// List<T>::POSIITON pos = list.GetFrontPosition();
// while (pos != list.GetEndPosition())
// {
//     T item;
//     hr = list.GetItemPos(&item);
//     pos = list.Next(pos);
// }

// The ComPtrList class template derives from List<> and implements a list of COM pointers.

template <class T>
struct NoOp
{
	void operator()(T& t)
	{
	}
};

template <class T>
class List
{
protected:

	// Nodes in the linked list
	struct Node
	{
		Node *prev;
		Node *next;
		T    item;

		Node() : prev(nullptr), next(nullptr)
		{
		}

		Node(T item) : prev(nullptr), next(nullptr)
		{
			this->item = item;
		}

		T Item() const { return item; }
	};

public:

	// Object for enumerating the list.
	class POSITION
	{
		friend class List < T > ;

	public:
		POSITION() : pNode(nullptr)
		{
		}

		bool operator==(const POSITION &p) const
		{
			return pNode == p.pNode;
		}

		bool operator!=(const POSITION &p) const
		{
			return pNode != p.pNode;
		}

	private:
		const Node *pNode;

		POSITION(Node *p) : pNode(p)
		{
		}
	};

protected:
	Node    m_anchor;  // Anchor node for the linked list.
	DWORD   m_count;   // Number of items in the list.

	Node* Front() const
	{
		return m_anchor.next;
	}

	Node* Back() const
	{
		return m_anchor.prev;
	}

	virtual HRESULT InsertAfter(T item, Node *pBefore)
	{
		if (pBefore == nullptr)
		{
			return E_POINTER;
		}

		Node *pNode = new Node(item);
		if (pNode == nullptr)
		{
			return E_OUTOFMEMORY;
		}

		Node *pAfter = pBefore->next;

		pBefore->next = pNode;
		pAfter->prev = pNode;

		pNode->prev = pBefore;
		pNode->next = pAfter;

		m_count++;

		return S_OK;
	}

	virtual HRESULT GetItem(const Node *pNode, T* ppItem)
	{
		if (pNode == nullptr || ppItem == nullptr)
		{
			return E_POINTER;
		}

		*ppItem = pNode->item;
		return S_OK;
	}

	// RemoveItem:
	// Removes a node and optionally returns the item.
	// ppItem can be nullptr.
	virtual HRESULT RemoveItem(Node *pNode, T *ppItem)
	{
		if (pNode == nullptr)
		{
			return E_POINTER;
		}

		assert(pNode != &m_anchor); // We should never try to remove the anchor node.
		if (pNode == &m_anchor)
		{
			return E_INVALIDARG;
		}


		T item;

		// The next node's previous is this node's previous.
		pNode->next->prev = pNode->prev;

		// The previous node's next is this node's next.
		pNode->prev->next = pNode->next;

		item = pNode->item;
		delete pNode;

		m_count--;

		if (ppItem)
		{
			*ppItem = item;
		}

		return S_OK;
	}

public:

	List()
	{
		m_anchor.next = &m_anchor;
		m_anchor.prev = &m_anchor;

		m_count = 0;
	}

	virtual ~List()
	{
		Clear();
	}

	// Insertion functions
	HRESULT InsertBack(T item)
	{
		return InsertAfter(item, m_anchor.prev);
	}


	HRESULT InsertFront(T item)
	{
		return InsertAfter(item, &m_anchor);
	}

	HRESULT InsertPos(POSITION pos, T item)
	{
		if (pos.pNode == nullptr)
		{
			return InsertBack(item);
		}

		return InsertAfter(item, pos.pNode->prev);
	}

	// RemoveBack: Removes the tail of the list and returns the value.
	// ppItem can be nullptr if you don't want the item back. (But the method does not release the item.)
	HRESULT RemoveBack(T *ppItem)
	{
		if (IsEmpty())
		{
			return E_FAIL;
		}
		else
		{
			return RemoveItem(Back(), ppItem);
		}
	}

	// RemoveFront: Removes the head of the list and returns the value.
	// ppItem can be nullptr if you don't want the item back. (But the method does not release the item.)
	HRESULT RemoveFront(T *ppItem)
	{
		if (IsEmpty())
		{
			return E_FAIL;
		}
		else
		{
			return RemoveItem(Front(), ppItem);
		}
	}

	// GetBack: Gets the tail item.
	HRESULT GetBack(T *ppItem)
	{
		if (IsEmpty())
		{
			return E_FAIL;
		}
		else
		{
			return GetItem(Back(), ppItem);
		}
	}

	// GetFront: Gets the front item.
	HRESULT GetFront(T *ppItem)
	{
		if (IsEmpty())
		{
			return E_FAIL;
		}
		else
		{
			return GetItem(Front(), ppItem);
		}
	}


	// GetCount: Returns the number of items in the list.
	DWORD GetCount() const { return m_count; }

	bool IsEmpty() const
	{
		return (GetCount() == 0);
	}

	// Clear: Takes a functor object whose operator()
	// frees the object on the list.
	template <class FN>
	void Clear(FN& clear_fn)
	{
		Node *n = m_anchor.next;

		// Delete the nodes
		while (n != &m_anchor)
		{
			clear_fn(n->item);

			Node *tmp = n->next;
			delete n;
			n = tmp;
		}

		// Reset the anchor to point at itself
		m_anchor.next = &m_anchor;
		m_anchor.prev = &m_anchor;

		m_count = 0;
	}

	// Clear: Clears the list. (Does not delete or release the list items.)
	virtual void Clear()
	{
		NoOp<T> clearOp;
		Clear<>(clearOp);
	}


	// Enumerator functions

	POSITION FrontPosition()
	{
		if (IsEmpty())
		{
			return POSITION(nullptr);
		}
		else
		{
			return POSITION(Front());
		}
	}

	POSITION EndPosition() const
	{
		return POSITION();
	}

	HRESULT GetItemPos(POSITION pos, T *ppItem)
	{
		if (pos.pNode)
		{
			return GetItem(pos.pNode, ppItem);
		}
		else
		{
			return E_FAIL;
		}
	}

	POSITION Next(const POSITION pos)
	{
		if (pos.pNode && (pos.pNode->next != &m_anchor))
		{
			return POSITION(pos.pNode->next);
		}
		else
		{
			return POSITION(nullptr);
		}
	}

	// Remove an item at a position. 
	// The item is returns in ppItem, unless ppItem is nullptr.
	// NOTE: This method invalidates the POSITION object.
	HRESULT Remove(POSITION& pos, T *ppItem)
	{
		if (pos.pNode)
		{
			// Remove const-ness temporarily...
			Node *pNode = const_cast<Node*>(pos.pNode);

			pos = POSITION();

			return RemoveItem(pNode, ppItem);
		}
		else
		{
			return E_INVALIDARG;
		}
	}

};



// Typical functors for Clear method.

// ComAutoRelease: Releases COM pointers.
// MemDelete: Deletes pointers to new'd memory.

class ComAutoRelease
{
public:
	void operator()(IUnknown *p)
	{
		if (p)
		{
			p->Release();
		}
	}
};

class MemDelete
{
public:
	void operator()(void *p)
	{
		if (p)
		{
			delete p;
		}
	}
};


// ComPtrList class
// Derived class that makes it safer to store COM pointers in the List<> class.
// It automatically AddRef's the pointers that are inserted onto the list
// (unless the insertion method fails). 
//
// T must be a COM interface type. 
// example: ComPtrList<IUnknown>
//
// NULLABLE: If true, client can insert nullptr pointers. This means GetItem can
// succeed but return a nullptr pointer. By default, the list does not allow nullptr
// pointers.

template <class T, bool NULLABLE = FALSE>
class ComPtrList : public List < T* >
{
public:

	typedef T* Ptr;

	void Clear()
	{
		ComAutoRelease car;
		List<Ptr>::Clear(car);
	}

	~ComPtrList()
	{
		Clear();
	}

protected:
	HRESULT InsertAfter(Ptr item, Node *pBefore)
	{
		// Do not allow nullptr item pointers unless NULLABLE is true.
		if (item == nullptr && !NULLABLE)
		{
			return E_POINTER;
		}

		if (item)
		{
			item->AddRef();
		}

		HRESULT hr = List<Ptr>::InsertAfter(item, pBefore);
		if (FAILED(hr) && item != nullptr)
		{
			item->Release();
		}
		return hr;
	}

	HRESULT GetItem(const Node *pNode, Ptr* ppItem)
	{
		Ptr pItem = nullptr;

		// The base class gives us the pointer without AddRef'ing it.
		// If we return the pointer to the caller, we must AddRef().
		HRESULT hr = List<Ptr>::GetItem(pNode, &pItem);
		if (SUCCEEDED(hr))
		{
			assert(pItem || NULLABLE);
			if (pItem)
			{
				*ppItem = pItem;
				(*ppItem)->AddRef();
			}
		}
		return hr;
	}

	HRESULT RemoveItem(Node *pNode, Ptr *ppItem)
	{
		// ppItem can be nullptr, but we need to get the
		// item so that we can release it. 

		// If ppItem is not nullptr, we will AddRef it on the way out.

		Ptr pItem = nullptr;

		HRESULT hr = List<Ptr>::RemoveItem(pNode, &pItem);

		if (SUCCEEDED(hr))
		{
			assert(pItem || NULLABLE);
			if (ppItem && pItem)
			{
				*ppItem = pItem;
				(*ppItem)->AddRef();
			}

			if (pItem)
			{
				pItem->Release();
				pItem = nullptr;
			}
		}

		return hr;
	}
};
